package structure.list;

/**
 * 该类用于创建链表，作用类似于java.util.LinkedList
 */
class CustomLinkedList {
    /** 链表头部 */
    private CustomLinkedListNode head;

    /** 构造链表时，链表头部节点的数据域为null */
    CustomLinkedList() {
        head = new CustomLinkedListNode(null);
    }

    /**
     * 向链表的末尾添加节点
     * @param element
     */
    void add(Object element) {
        CustomLinkedListNode temp = head;
        // 如果存在下一个节点
        while (temp.getNext() != null) {
            // 将下一个节点赋值给temp
            temp = temp.getNext();
        }
        temp.setNext(new CustomLinkedListNode(element));
    }

    /**
     * 遍历并打印链表中的每个节点的元素
     */
    void display() {
        int index = 0;
        // 获取头部节点的下一个节点
        CustomLinkedListNode temp = head.getNext();
        // 如果该节点不为null
        while (temp != null) {
            if (index < size() - 1) {
                // 获取该节点的数据域
                System.out.print(temp.getElement() + "\t");
            } else {
                System.out.print(temp.getElement());
            }
            // 返回temp的下一个节点并赋值给temp
            temp = temp.getNext();
            index++;
        }
        System.out.println();
    }

    /**
     * 根据指定数据查找数据域匹配的节点
     * @param element
     * @return
     */
    int indexOf(Object element) {
        int nowIndex = 0;
        CustomLinkedListNode temp = head.getNext();
        while (temp != null) {
            if (temp.getElement().equals(element)) {
                return nowIndex;
            }
            temp = temp.getNext();
            nowIndex++;
        }
        return -1;
    }

    /**
     * 获取指定索引的节点
     * @param index
     * @return
     */
    Object get(int index) {
        // 设置当前索引为0
        int nowIndex = 0;
        // 设置当前节点为紧邻头节点之后的节点
        CustomLinkedListNode node = head.getNext();
        while (node != null) {
            if (nowIndex == index) {
                return node.getElement();
            }
            node = node.getNext();
            nowIndex++;
        }
        return null;
    }

    /**
     * 返回链表中的节点数量
     * @return
     */
    int size() {
        int count = 0;
        CustomLinkedListNode temp = head.getNext();
        while (temp != null) {
            temp = temp.getNext();
            count++;
        }
        return count;
    }

    /**
     * 在链表的指定位置插入节点
     * 在插入新节点后，原位置及之后的节点将向后移动1个单位
     * @param index 索引值
     * @param element 节点内的元素
     */
    void insert(int index, Object element) {
        int nowIndex = 0;
        // 声明并定义一个临时节点temp（链表头部节点）
        CustomLinkedListNode temp = head;
        // 如果temp不为空
        while (temp != null) {
            // 如果当前索引等于给定索引
            if (nowIndex == index) {
                CustomLinkedListNode node = new CustomLinkedListNode(element);
                // 将temp的下一个节点设置为node的下一个节点
                node.setNext(temp.getNext());
                // 将node设置为temp的下一个节点
                temp.setNext(node);
            }
            temp = temp.getNext();
            nowIndex++;
        }
    }

    /**
     * 删除链表中指定位置的节点，返回移除的元素
     * @param index
     */
    Object remove(int index) {
        // 声明并定义一个临时节点temp（链表头部节点）
        CustomLinkedListNode temp = head;
        // 声明并定义一个临时节点tempNext（链表头部的下一个节点）
        CustomLinkedListNode tempNext = head.getNext();
        Object element = get(index);
        // 当tempNext不为null
        while (tempNext != null) {
            // 如果tempNext的元素与list指定位置存储的元素相等
            if (tempNext.getElement().equals(element)) {
                // 将tempNext的下一个节点设置为temp的下一个节点
                temp.setNext(tempNext.getNext());
            }
            temp = tempNext;
            tempNext = tempNext.getNext();
        }
        return element;
    }

    /**
     * 自定义链表节点
     * 第一个节点的数据域为null
     * 最后一个节点的链域为null
     */
    private class CustomLinkedListNode {
        /** 节点数据域 */
        private Object element;
        /** 节点链域 */
        private CustomLinkedListNode next;
    
        /**
         * 获取该节点的下一个节点
         * @return
         */
        private CustomLinkedListNode getNext() {
            return next;
        }
    
        /**
         * 设置该节点的下一个节点
         * @param next
         */
        private void setNext(CustomLinkedListNode next) {
            this.next = next;
        }
    
        /** 获取该节点存储的元素 */
        private Object getElement() {
            return element;
        }
    
        /**
         * 创建新节点
         * @param element
         */
        private CustomLinkedListNode(Object element) {
            this.element = element;
            // 创建的节点在被添加至某个链表之前，默认没有下一个节点
            setNext(null);
        }
    }
}
